package com.tgy.programmer_code_interview_guide._03_binarytree;


import com.tgy.common.printer.BinaryTreeInfo;
import com.tgy.common.printer.BinaryTrees;
import com.tgy.leetcode.Node;
import com.tgy.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class BinaryTree{

    public static TreeNode generalTreeByPreorderAndInorder(int[] preorder, int[] inorder) {

//        int[] preorders = {1,2,4,5,8,9,3,6,7};
//        int[] inorders = {4,2,8,5,9,1,6,3,7};

        Stack<TreeNode> stack = new Stack<>();

        TreeNode root = new TreeNode(preorder[0]);
        int preIndex = 1,inIndex = 0;
        TreeNode node = root;
        stack.push(node);
        while (preIndex < inorder.length && inIndex < inorder.length) {

            int val = inorder[inIndex];
            while (preorder[preIndex - 1] != val) {
                node.left = new TreeNode(preorder[preIndex]);
                stack.push(node.left);
                node = node.left;
                preIndex++;
            }

            while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {

                node = stack.pop();
                inIndex++;
            }

            node.right = new TreeNode(preorder[preIndex]);
            stack.push(node.right);
            node = node.right;
            preIndex++;

        }


        return root;
    }

    public static TreeNode generalTreeByPreorderAndInorder01(int[] preorder, int[] inorder) {

        Map<Integer,Integer> locations =  new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {

            locations.put(inorder[i],i);
        }

        return traversal(preorder,0,preorder.length - 1, inorder,0, inorder.length - 1,locations);
    }

    private static TreeNode traversal(int[] preorder, int p1, int p2, int[] inorder, int i1, int i2, Map<Integer,Integer> locations) {

        if (i1 > i2) {

            return null;
        }

        int val = preorder[p1];
        TreeNode node = new TreeNode(val);

        int len = locations.get(val) - i1;

        node.left = traversal(preorder,p1 + 1,p1 + len,inorder,i1,i1+ len - 1,locations);
        node.right = traversal(preorder,p1+len + 1,p2,inorder,i1 +len + 1,i2,locations);

        return node;
    }


}


public class _21_重构二叉树 {

    public static void main(String[] args) {

        int[] preorders = {1,2,4,5,8,9,3,6,7};
        int[] inorders = {4,2,8,5,9,1,6,3,7};
        TreeNode treeNode = BinaryTree.generalTreeByPreorderAndInorder(preorders, inorders);

        BinaryTrees.print(new BinaryTreeInfo() {
            @Override
            public Object root() {
                return treeNode;
            }

            @Override
            public Object left(Object node) {
                return ((TreeNode)node).left;
            }

            @Override
            public Object right(Object node) {
                return ((TreeNode)node).right;
            }

            @Override
            public Object string(Object node) {
                return ((TreeNode)node).val;
            }
        });
    }

}
